/*
 * @lc app=leetcode.cn id=1711 lang=typescript
 *
 * [1711] 大餐计数
 */

// @lc code=start
function countPairs(deliciousness: number[]): number {
  const maxValue = Math.max(...deliciousness);
  // 当前数组所能获得最大的幂
  const maxSum = maxValue * 2;
  // 统计数组中数字出现的次数
  const hash: Map<number, number> = new Map();
  const m = deliciousness.length;
  const mod = 10 ** 9 + 7;
  let ans = 0;
  for (let i = 0; i < m; i++) {
    const value = deliciousness[i];
    // 遍历[1,maxSum]中所有2的幂，查看哈希表中是否有能凑合和的另一个数的数量
    for (let k = 1; k <= maxSum; k <<= 1) {
      const count = hash.get(k - value) || 0;
      ans = (ans + count) % mod;
    }
    hash.set(value, (hash.get(value) || 0) + 1);
  }
  return ans;
}
// @lc code=end
